package dynamic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 带备忘录的递归解法
 */
public class Fibonacci {
    public static int fib(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        return innerFib(map, n);
    }

    private static int innerFib(Map<Integer, Integer> map, int n) {
        if (n == 1 || n == 2) return 1;
        if (map.get(n) != null) {
            return map.get(n);
        }
        int result = innerFib(map, n - 1) + innerFib(map, n - 2);
        map.put(n, result);
        return result;
    }

    public static int fibDp(int n) {
        List<Integer> dp = new ArrayList<>(n + 1);
        dp.add(1, 1);
        dp.add(2, 1);
        for (int i = 3;i <= n; i++) {
            dp.set(i, dp.get(i - 1) + dp.get(i - 2));
        }
        return dp.get(n);
    }

    public static int fib2(int n) {
        if (n == 2 || n == 1)
            return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}

